#include <tr1/unordered_map>
#include <vector>
#include <string>
#include <map>

using namespace std;

namespace ads {
class PrefixTree {
 public:
  PrefixTree();
  ~PrefixTree();
  void insert(const string& str);
  bool mark_remove(const string& str);
  void complete(const string& pre, vector<string>* rest);
 private:
  void complete(PrefixTree* root, const string& pre, size_t pos, string newstr, multimap<int, string>* rest);
  void insert(PrefixTree* root, const string& pre, size_t pos);
  bool find(PrefixTree* root, const string& pre, size_t pos);
  bool mark_remove(PrefixTree* root, const string& pre, size_t pos);

  tr1::unordered_map<char, PrefixTree*> nodes;
  int value;
};
}  // using namespace ads
